package fun.coding.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class FourSum {

	public static void main(String[] args) {
		FourSum ins = new FourSum();
		int[] test1 = {1, 0, -1, 0, -2, 2};
		int target1 = 0;
		List<List<Integer>> res1 = ins.fourSum(test1, target1);
		LeetCodeHelpers.printGenericList(res1);

		int[] test2 = {-3,-2,-1,0,0,1,2,3};
		int target2 = 0;
		List<List<Integer>> res2 = ins.fourSum(test2, target2);
		LeetCodeHelpers.printGenericList(res2);

	}
	
	public List<List<Integer>> fourSum(int[] num, int target) {
		List<List<Integer>> res = new LinkedList<List<Integer>>();
		if (num == null || num.length < 4) return res;
		
		Arrays.sort(num);
		
		int size = num.length;
		
		for (int i = 0; i < size; i++) {
			if (i - 1 >= 0 && num[i] == num[i - 1]) {
				continue;
			}
			
			for (int j = i + 1; j < size; j++) {
				if (j - 1 >= i + 1 && num[j] == num[j - 1]) {
					continue;
				}
				
				int l = j + 1;
				int r = size - 1;
				int newTarget = target - num[i] - num[j];
				while (l < r) {
					int sum = num[l] + num[r];
					if (sum == newTarget) {
						List<Integer> sol = new LinkedList<Integer>();
						sol.add(num[i]);
						sol.add(num[j]);
						sol.add(num[l]);
						sol.add(num[r]);
						res.add(sol);
						
						// Pay attention to the logic here, multiple ways to implement it to skip dup
						l++;
						r--;
						while (l < size && num[l] == num[l - 1]) l++;
						while (r >= 0 && num[r] == num[r + 1]) r--;
					} else if (sum > newTarget) {
						r--;
					} else {
						l++;
					}
				}
			}
		}
		return res;
	}

}
